package xyf.p04.tree;

/**
 * ClassName: J036_Convert2Node
 * Description:
 * Author: xyf
 * Date: 9/9/22 9:44 AM
 * Version: 1.0
 **/
public class J036_Convert2Node
{
    class Node
    {
        public int val;
        public Node left;
        public Node right;

        public Node()
        {
        }

        public Node(int _val)
        {
            val = _val;
        }

        public Node(int _val, Node _left, Node _right)
        {
            val = _val;
            left = _left;
            right = _right;
        }
    }

    private Node dummyHead = new Node();

    private Node tail = dummyHead;

    public Node treeToDoublyList(Node root)
    {
        if (root == null)
        {
            return null;
        }

        dfs(root);

        tail.right = dummyHead.right;
        dummyHead.right.left = tail;

        return dummyHead.right;
    }

    private void dfs(Node cur)
    {
        if (cur == null)
        {
            return;
        }

        dfs(cur.left);

        cur.left = tail;
        tail.right = cur;
        tail = cur;

        dfs(cur.right);
    }
}